package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/balanced-binary-tree/">平衡二叉树(Balanced Binary Tree)</a>
 * <p>给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。</p>
 * <pre>
 * 示例 1：
 *      输入：root = [3,9,20,null,null,15,7]
 *      输出：true
 *
 * 示例 2：
 *      输入：root = [1,2,2,3,3,null,null,4,4]
 *      输出：false
 *
 * 示例 3：
 *      输入：root = []
 *      输出：true
 * </pre>
 * <b>提示：</b>
 * <ul>
 *     <li>树中的节点数在范围 [0, 5000] 内</li>
 *     <li>-10^4 <= Node.val <= 10^4</li>
 * </ul>
 *
 * @author c2b
 * @since 2023/5/11 13:18
 */
public class LC0110IsBalanced_S {

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        return Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(height(root.left), height(root.right)) + 1;
    }
}
